﻿
P12176[蓝桥杯 2025 省 Python B] 书架还原
返回题目加入题单复制题目

题目描述
在一个偏远的图书馆里，有个书架上放着 n 本书，每本书上都标有一个从 1 到 n 的唯一编号。

按照规矩，这些书应该按编号从小到大依次排列：1 号书位于最左端，2 号书紧随其后，以此类推，直到 n 号书在最右端。这样的顺序不仅看起来整齐，也方便读者快速找到想借的书。

可昨天店里人来人往，借书还书忙得不可开交，书架上的顺序出现了错乱。现在，书架上的书变成了 a = (a
	1
	​
	, a
	2
	​
	, …, a
	n
	​
	)，其中 a
	i
	​
	表示第 i 个位置上的书编号。

	管理员决定动手整理书架，但时间有限，他希望用最少的操作把书的顺序恢复到正确的排列。每次操作，他可以挑选书架上任意两本书，交换它们的位置。例如，如果当前排列是(3, 1, 2)，他可以交换第 1 本和第 2 本，得到(1, 3, 2)，再交换第 2 本和第 3 本，得到(1, 2, 3)。

	你的任务是帮助管理员计算，最少需要进行多少次操作，才能让书架上的书的编号排列变为(1, 2, …, n)。

	输入格式
	输入的第一行包含一个正整数 n，表示书架上书的总数。

	第二行包含 n 个正整数 a
	1
	​
	, a
	2
	​
	, …, a
	n
	​
	，相邻整数之间使用一个空格分隔，依次表示当前书架上每本书的编号。a
	1
	​
	, a
	2
	​
	, …, a
	n
	​
	是一个 1 到 n 的排列。

	输出格式
	输出一行包含一个整数表示答案，即将书架上的书恢复到正确排列所需的最少操作次数。

	输入输出样例
	输入 #1复制
	3
	3 1 2
	输出 #1复制
	2
	说明 / 提示
	评测用例规模与约定
	对于 30 % 的评测用例，1≤n≤10
	3
	，1≤a
	i
	​
	≤n，a
	1
	​
	, a
	2
	​
	, …, a
	n
	​
	各不相同；
	对于所有评测用例，1≤n≤10
	6
	，1≤a
	i
	​
	≤n，a
	1
	​
	, a
	2
	​
	, …, a
	n
	​
	各不相同。

	//错误的贪心就是：认为每交换一次就符合一个要求->n-1次即可；但是有可能会导致交换一次符合两个位置。
//思路：贪心+hash：此题可以看出每次我们只要交换一次至少保证符合一个位置一一对应的要求即可；此时我们就要根据对应位置的下标找到对应的val然后给它交换一下：因此又引出了hash绑定：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int h[N] = { 0 };//hash[val]<->此时对应下标绑定
int main() {
	int n;
	cin >> n;
	int ans = 0;
	vector<int>v(n + 1);
	//完成绑定hash关系：
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
		h[v[i]] = i;
	}
	for (int i = 1; i <= n; i++) {
		if (v[i] != i) {
			swap(v[i], v[h[i]]);//遍历到i位置就让它符合一一对应要求；然后交换
			ans++;
			//更新新的hash映射关系：
			int tmp = v[i];
			v[i] = h[v[h[i]]];
			h[v[h[i]]] = h[tmp];


		}
	}
	cout << ans << endl;

}
